package com.Questions.DP;

import java.util.*;
/**
 *  自由之路
 */
public class leetcode514 {
    // 定义dp[i][j] 表示从前往后写出key的第i个字符
    // ring的第j个字符与12：00方向对齐的最少步数

    // 对每一个字符维护pos[i] 表示字符i在ring中出现的位置集合
    // 枚举上一次与12 方向对齐的位置k 列出如下的转移方程
    // dp[i][j]= {dp[i−1][k]+min{abs(j−k),n−abs(j−k)}+1}
    //对于每一个k∈pos[key[i−1]] 取其中对最小值

    //
    public int findRotateSteps(String ring, String key) {
        int n=ring.length();
        int m=key.length();
        List<Integer>[] pos=new List[26];
        for(int i=0;i<26;++i){
            pos[i]=new ArrayList<Integer>();
        }
        for(int i=0;i<n;++i){// 每一个字符出现的位置集合
            pos[ring.charAt(i)-'a'].add(i);
        }
        int[][] dp=new int[m][n];
        for(int i=0;i<m;++i){// 初始化为无穷以便最后取最小值
            Arrays.fill(dp[i],0x3f3f3f);
        }
        for(int i:pos[key.charAt(0)-'a']){
            // 将第一个key中出现的字符 找到ring对应的位置
            dp[0][i]=Math.min(i,n-i) +1;
        }
        for(int i=1;i<m;++i){
            for(int j:pos[key.charAt(i)-'a']){
                for(int k:pos[key.charAt(i-1)-'a']){
                    // 对于key中第i个字符 其在ring中的每一个位置j
                    // 以及key中第i-1个字符 其在ring中的每一个位置k
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + Math.min(Math.abs(j - k), n - Math.abs(j - k)) + 1);
                }
            }
        }
        return Arrays.stream(dp[m - 1]).min().getAsInt();
    }
}
